/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        unordered_map<TreeNode *, TreeNode *> parentMap;
        recursiveAddToParentMap(root, nullptr, parentMap);
        unordered_set<TreeNode *> visited;
        while (p != nullptr)
        {
            visited.insert(p);
            p = parentMap[p];
        }
        while (!visited.count(q))
        {
            q = parentMap[q];
        }
        return q;
    }

    void recursiveAddToParentMap(TreeNode *node, TreeNode *parent, unordered_map<TreeNode *, TreeNode *> &map)
    {
        if (node == nullptr)
        {
            return;
        }
        map[node] = parent;
        recursiveAddToParentMap(node->left, node, map);
        recursiveAddToParentMap(node->right, node, map);
    }
};